{
 "cells": [
  {
   "cell_type": "raw",
   "id": "e8d825ec",
   "metadata": {},
   "source": [
    "2.1 插入排序\n",
    "把 给定的数组中的元素插入到一个新的数组中，得到一个完整的有序数组；\n",
    "时间复杂度： O(n^2)\n",
    "空间复杂度： O(1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "80ea4c0d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8]\n"
     ]
    }
   ],
   "source": [
    "nums = [5,3,6,4,1,2,8,7]\n",
    "\n",
    "for i in range(1, len(nums)): # 遍历未排序元素\n",
    "    for j in range(i): # 遍历已排序的元素， 下标小于当前元素的所有元素\n",
    "        if nums[i] < nums[j]:\n",
    "            ins = nums[i]\n",
    "            nums.pop(i)\n",
    "            nums.insert(j, ins) # 插入到第一个大于它的数据之前\n",
    "            break\n",
    "print(nums)"
   ]
  },
  {
   "cell_type": "raw",
   "id": "9135caf6",
   "metadata": {},
   "source": [
    " 2.1.2 选择排序\n",
    "\n",
    "从无序数组中， 每次选择最大或最小的数据， 从无序数组中放到有序数组的末尾，达到排序效果。\n",
    "时间复杂度： O(n^2)\n",
    "不稳定排序算法\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "99b52c84",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8]\n"
     ]
    }
   ],
   "source": [
    "nums = [5,3,6,4,1,2,8,7]\n",
    "\n",
    "res = []\n",
    "\n",
    "while (len(nums)):\n",
    "    minInd = 0 # 最小数的下标；\n",
    "    for i in range(1, len(nums)):    \n",
    "        if nums[minInd] > nums[i]:\n",
    "            minInd = i\n",
    "            \n",
    "    \n",
    "    res.append(nums[minInd])\n",
    "    # temp = nums[minInd]\n",
    "    # res.append(temp)\n",
    "    nums.pop(minInd)\n",
    "    \n",
    "print(res)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "eb11ee98",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8]\n"
     ]
    }
   ],
   "source": [
    "nums = [5,3,6,4,1,2,8,7]\n",
    "\n",
    "# 在原数组上排序， 将最小的放到左边已经排序好的地方\n",
    "\n",
    "for i in range(0, len(nums)):    \n",
    "    for j in range(i, len(nums)):\n",
    "        if nums[j] < nums[i]:\n",
    "            nums[i], nums[j] = nums[j], nums[i]\n",
    "            \n",
    "print(nums)"
   ]
  },
  {
   "cell_type": "raw",
   "id": "6fdd4f78",
   "metadata": {},
   "source": [
    "2.1.3 冒泡排序\n",
    "重复遍历数组， 并依次比较相邻元素的方法来排序。\n",
    "\n",
    "时间复杂度： O(n^2)   最好是O(n)\n",
    "空间复杂度O(1)\n",
    "\n",
    "每执行一遍， 都能把最大的数据放到最后一个"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "817fad19",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8]\n"
     ]
    }
   ],
   "source": [
    "nums = [5,3,6,4,1,2,8,7]\n",
    "\n",
    "for i in range(len(nums), 0, - 1):\n",
    "    flag = 0\n",
    "    for j in range(0, i - 1):\n",
    "        if nums[j] > nums[j +1]:\n",
    "            nums[j], nums[j + 1] = nums[j + 1], nums[j]\n",
    "            flag = 1\n",
    "            \n",
    "    if not flag:\n",
    "        break # 节省时间\n",
    "        \n",
    "print(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "1bb1b591",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "print(int(5 / 2))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f9bfa5fd",
   "metadata": {},
   "source": [
    "# 高级排序算法\n",
    "\n",
    "2.2.1 归并排序\n",
    "\n",
    "归一、合并。\n",
    "先把数列 拆分成子数列， 对子序列进行排序后， 再把有序的子数列合并为完整的有序数据的算法。\n",
    "时间复杂度： O(nlgn)\n",
    "空间复杂度：O(1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "ab1f1a3a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8]\n"
     ]
    }
   ],
   "source": [
    "nums = [5,3,6,4,1,2,8,7]\n",
    "\n",
    "def MergeSort(num):\n",
    "    if (len(num) <= 1):\n",
    "        return num\n",
    "    \n",
    "    mid = int(len(num) / 2)\n",
    "    llist, rlist = MergeSort(num[:mid]), MergeSort(num[mid:])\n",
    "    \n",
    "    result = []\n",
    "    i, j = 0, 0\n",
    "    while (i < len(llist) and j   < len(rlist)):\n",
    "        if rlist[j] < llist[i]:\n",
    "            result.append(rlist[j])\n",
    "            j+=1\n",
    "        else:\n",
    "            result.append(llist[i])\n",
    "            i += 1\n",
    "    \n",
    "    result += llist[i:] + rlist[j:] # 未添加的部分加到结果数组末尾\n",
    "    \n",
    "    return result\n",
    "\n",
    "print(MergeSort(nums))\n",
    "    \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "28a62c48",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "raw",
   "id": "04f2f6fd",
   "metadata": {},
   "source": [
    "快速排序\n",
    "取数组中的一个数作为基准值， 把所有的小于基准值的数都放在它的一测， 再把所有大于基准值的数都放到它的另一侧； 随后对基准值左右两侧的数组分别进行快速排序。 （也是递归进行的）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "ea83eb5c",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8]\n"
     ]
    }
   ],
   "source": [
    "nums = [5,3,6,4,1,2,8,7]\n",
    "# 基础班\n",
    "def QuickSort(num):\n",
    "    if len(num) <= 1: # 边界条件\n",
    "        return num\n",
    "    \n",
    "    key = num[0] # 基准数\n",
    "    \n",
    "    llist, rlist, midlist = [], [], [key]\n",
    "    for i in range(1, len(num)):\n",
    "        if num[i] < key:\n",
    "            llist.append(num[i])\n",
    "        elif num[i] > key:\n",
    "            rlist.append(num[i])\n",
    "        else:\n",
    "            midlist.append(num[i])\n",
    "            \n",
    "    return QuickSort(llist) + midlist + QuickSort(rlist)\n",
    "\n",
    "print(QuickSort(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "ce73a4fa",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8]\n"
     ]
    }
   ],
   "source": [
    "nums = [5,3,6,4,1,2,8,7]\n",
    "\n",
    "def QSort(left, right): # 原地版\n",
    "    if left > right: # 边界条件\n",
    "        return\n",
    "    \n",
    "    l,r, key = left, right, nums[left]\n",
    "    \n",
    "    while(l < r):\n",
    "        while( l < r and nums[r] >= key):\n",
    "            r -= 1\n",
    "        nums[l] = nums[r]\n",
    "    \n",
    "        while l < r and nums[l] < key:\n",
    "            l += 1\n",
    "        nums[r] = nums[l]\n",
    "        \n",
    "    nums[l] = key # 把基准值赋值给左指针和右指针共同指向的位置\n",
    "    \n",
    "    QSort(left, l - 1)\n",
    "    \n",
    "    QSort(l + 1, right)\n",
    "    \n",
    "QSort(0, len(nums) - 1)\n",
    "\n",
    "print(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c8da7350",
   "metadata": {},
   "source": [
    "# 2.2.3 希尔排序\n",
    "\n",
    "缩小增量排序。 对插入排序进行优化后产生的一种排序算法。\n",
    "思路： 把数组内的元素按下表增量分组， 对每一组元素进行插入排序后， 缩小增量并重复之前的步骤， 直到增量达到1；\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "99238f4a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8]\n"
     ]
    }
   ],
   "source": [
    "nums = [5,3,6,4,1,2,8,7]\n",
    "\n",
    "def ShellSort(nums):\n",
    "    step = len(nums) // 2 # 初始化增量为数组长度的一半\n",
    "    while step > 0:\n",
    "        for i in range(step, len(nums)):\n",
    "            ind = i\n",
    "            while ind  >= step and nums[ind] < nums[ind - step]:\n",
    "                nums[ind],  nums[ind - step] = nums[ind - step], nums[ind]\n",
    "                ind -= step\n",
    "                \n",
    "        # 每循环一次， 都把小的放到了前面；\n",
    "        \n",
    "        step //=2\n",
    "    print(nums)\n",
    "    \n",
    "ShellSort(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "447cf242",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "1 //2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c15f3764",
   "metadata": {},
   "source": [
    "# 2.2.4  堆排序\n",
    "\n",
    "把数组构建成一棵二叉树，并随着每次堆的变化更新堆顶的最大、最小值；\n",
    "\n",
    "时间复杂度： O(nlgn)\n",
    "\n",
    "大顶堆、小顶堆\n",
    "\n",
    "特定：\n",
    "父亲节点的下标是n， 左子节点下标是2n， 右子节点下标是2n + 1\n",
    "\n",
    "因为数组的小标从0开始， 而堆的编号从1开始， 所以数组的第一个位置留空。\n",
    "nums.insert(0,0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "312d9d90",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 999, 953, 112, 678, 113, 61, 43, 72, 310, 34, 93, 1, 32, 3, 15, 5, 20, 2, 8, 4, 3, 2]\n"
     ]
    }
   ],
   "source": [
    "nums = [4,2,61,8,953,1,3,72,310,113,93,112,32,43,15,5,20,999,678,34,3,2]\n",
    "\n",
    "def Heapify(start, end): # 向下调整的函数， 传入数据为堆顶节点的编号和堆末尾的界限值   只调整一个堆\n",
    "    father = start\n",
    "    son = father * 2 # 左子节点\n",
    "    while son < end:\n",
    "        # 如果存在右节点且其值大于左子节点的值， son存储右子节点的编号\n",
    "        if son + 1 < end and nums[son + 1] > nums[son]:\n",
    "            son += 1\n",
    "            \n",
    "        if nums[father] < nums[son]: # 如果父节点小于子节点\n",
    "            nums[father], nums[son] = nums[son], nums[father]\n",
    "            father = son # 进入下一层继续调整\n",
    "            son = father * 2\n",
    "        else:\n",
    "            return\n",
    "        \n",
    "def HeapInit():\n",
    "    nums.insert(0,0)\n",
    "    for i in range((len(nums) - 1)//2, 0, -1): # 从最底层最右侧的非叶子结点开始调整\n",
    "        Heapify(i, len(nums) - 1)\n",
    "            \n",
    "def HeapSort(): # 堆排序函数\n",
    "    for i in range(len(nums) -1, 0, -1): # 从堆末尾开始进行元素交换\n",
    "        nums[1], nums[i] = nums[i], nums[1] \n",
    "        \n",
    "        Heapify(1, i - 1)\n",
    "        \n",
    "HeapInit()\n",
    "# HeapSort()\n",
    "\n",
    "print(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "9862bb38",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 4, 2, 61, 8, 953, 1, 3, 72, 310, 113, 93, 112, 32, 43, 15, 5, 20, 999, 678, 34, 3, 2]\n"
     ]
    }
   ],
   "source": [
    "nums = [4,2,61,8,953,1,3,72,310,113,93,112,32,43,15,5,20,999,678,34,3,2]\n",
    "nums.insert(0,0)\n",
    "print(nums)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e6e9fca",
   "metadata": {},
   "source": [
    "# 桶排序\n",
    "\n",
    "将每个数都放到桶里进行排序。\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
